#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/longest-increasing-subsequence/

class Solution {
    int ret = 0;
    vector<int> memory;
    int n;
public:
    int lengthOfLIS(vector<int>& nums) {
        n = nums.size();
        memory.resize(n);
        for (int i = 0; i < n; i++)
        {
            ret = max(ret, dfs(nums, i));
        }
        return ret;
    }

    int dfs(vector<int>& nums, int pos)
    {
        if (memory[pos] != 0) return memory[pos];

        int sum = 1;
        for (int i = pos + 1; i < n; i++)
        {
            if (nums[i] > nums[pos])
            {
                sum = max(sum, dfs(nums, i) + 1);
            }
        }
        memory[pos] = sum;
        return sum;
    }
};